const common = require('./base/common');

/**
 * 424. 替换后的最长重复字符
 * 
 * Note:
 * 1. 窗口一旦扩张就不会收缩，窗口最后会保持最长字符串匹配的宽度；
 * 2. 记录的最长字符串的相同字符数目，精妙之处在于，只有当后续窗口中的相同字符超过其值时，才会继续扩张窗口，否则一直滑动；
 * 
 * @param {string} s 
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
    let left = 0, dict = {}, maxCharsNum = 0;

    for(let right=0; right < s.length; ++right) {
        dict[s[right]] = dict[s[right]]? dict[s[right]] + 1: 1;
        maxCharsNum = Math.max(maxCharsNum, dict[s[right]]);
        if(maxCharsNum + k < right - left + 1) {
            dict[s[left]]--;
            ++left;
        }
    }

    return s.length - left;
};

common.testing([
    ["BAAAABCCACCCC", 1], 
    ["BAAACCCCCABCAAAA", 2],
    ["ABCDEFEDCBA", 3]
])((test) => characterReplacement(test[0], test[1]));